#ifndef __SUDOKU_H__
#define __SUDOKU_H__
#include <vector>
using namespace std;
/*
* leetcode 37 解数独
* 
* 数独的解法需 遵循如下规则：
*	数字 1-9 在每一行只能出现一次。
*	数字 1-9 在每一列只能出现一次。
*	数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
*/

/*
* 解数独 和 N皇后问题类似, 可以通过棋盘穷举来获取最终结果
* 
* 与 N皇后不同的是
*	N皇后的每层递归遍历行, 递归时通过 for 循环遍历每一列, 来确定每一个位置能否放置皇后
*	而解数独不同, N皇后只在每一行(列)中放置一个皇后, 而解数独是放置九个数
*		另外, 关于放置内容, N皇后 是一行放置完后, 放置下一行, 即深度递归
*		而 解数独 不同, 在放置完内容后, 会往下一个格子放置内容
* 所以其实是多了一个维度
* 
* 解法: 二维递归
*	即两个 for 循环, 再进行递归
* 
* 树形结构就不画了, 有丶大, 参考 https://www.programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html
*/

/*
* 这里就不搜集所有结果, 只收集一个, 即一找到结果就立刻停止回溯
*/
bool IsSudokuValid(const vector<vector<char>>& board, int row, int col, char num);

bool BackTrackingSudoku(vector<vector<char>>& board) {
	//不能再像 N皇后 一样, 必须每个格子都进行填充
	/*
	* if (row == board.size()) {
	*	results.push_back(board);
	*	return;
	* }
	*/
	for (int row = 0; row < board.size(); row++) {
		for (int col = 0; col < board.size(); col++) {
			if (board[row][col] != '.')
				continue;

			for (int i = 1; i <= 9; i++) {
				char c = '0' + i;
				if (IsSudokuValid(board, row, col, c)) {
					board[row][col] = c;

					//搜索到结果, 不继续搜索, 直接 return true
					if (BackTrackingSudoku(board))
						return true;

					board[row][col] = '.';
				}
			}
			//试了九个数, 找不到结果, 直接return false
			return false;
		}
	}

	//从上层递归传入, 此时 row == board.size()
	return true;
}

void BackTrackingSudokuII(vector<vector<char>>& board, vector<vector<vector<char>>>& results) {
	for (int row = 0; row < board.size(); row++) {
		for (int col = 0; col < board.size(); col++) {
			if (board[row][col] != '.')
				continue;

			for (int i = 1; i <= 9; i++) {
				char c = '0' + i;
				if (IsSudokuValid(board, row, col, c)) {
					board[row][col] = c;

					BackTrackingSudokuII(board, results);

					board[row][col] = '.';
				}
			}
			//试了九个数, 找不到结果, 直接return
			return;
		}
	}

	results.push_back(board);
	//从上层递归传入, 此时 row == board.size()
	return;
}

bool IsSudokuValid(const vector<vector<char>>& board, int row, int col, char num) {
	for (int c = 0; c < board.size(); c++)
		if (board[row][c] == num)
			return false;

	for (int r = 0; r < board.size(); r++)
		if (board[r][col] == num)
			return false;

	int startRow = (row / 3) * 3;
	int startCol = (col / 3) * 3;

	for (int c = startCol; c < startCol + 3; c++)
		for (int r = startRow; r < startRow + 3; r++)
			if (board[r][c] == num)
				return false;

	return true;
}

#endif // !__SUDOKU_H__

